Digital shape reconstruction is a field that focuses on converting physical objects into digital representations. Various 3D scanning technologies are available that collect sample data points on a surface of a physical object, and well-established techniques exist to convert the data points into dense or decimated polygonal meshes, which need to be further converted into representations suitable for CAD, CAM, and CAE. A challenge in this field is to automate the conversion process while producing digital models that meet the requirements of downstream applications, including both an accurate representation of the features of the models and a high degree of smoothness. The first step to reach this goal is to partition three-dimensional object data, including point clouds and related polygonal meshes into appropriate regions. A so-called segmenting curve network is also created that determines the boundary curves of these regions. Regions are pre-images of the faces of a final CAD model, and, in a later phase of digital shape reconstruction, each region may be approximated by a single or composite surface.
Techniques for generating digital models may utilize results from Combinatorial Morse Theory. One aspect of this theory is the analysis of functions defined over manifolds, represented as polygonal meshes produced from point clouds. Each function is assumed to be piecewise linear, approximating an unknown smooth function. To analyze this function means identifying its main features, which are defined in terms of critical points and connections between them. For surfaces (2 manifolds) there are only three types of non-degenerate critical points: minima, saddles, and maxima. The Morse complex draws curves between the saddles and the minima, forming a curve network that decomposes the surface into simple monotonic regions, one for each maximum. This theory can be utilized to construct a natural region structure that adapts to the features of the object.
In Computer Aided Design (CAD) and, in particular, in mechanical engineering, objects are composed of (i) relatively large, functional surfaces connected by (ii) highly-curved transitions, which are often called connecting features, and (iii) vertex blends at their junctions. A CAD model is a collection of stitched faces that lie on various types of implicit, parametric and special surfaces. The related representational and algorithmic issues associated with CAD model generation have been deeply studied in the computer aided geometric design literature. The goal of digital shape reconstruction is to find a faithful and geometrically well-aligned region structure, which corresponds to the above surface hierarchy and makes it possible to approximate regions by using standard CAD surfaces.
The term “segmentation” is frequently used in the digital shape reconstruction literature, but this needs to be distinguished from segmentation techniques applied in image processing, where mostly bitmaps and concise visual information are the focus. Triangulated 2-manifolds have been studied in the field of computer graphics and geometric processing. There have also been efforts to construct feature-adapting quadrangulations using Voronoi diagrams or exploit geometric information accumulated by surface decimation algorithms. Conventional techniques to reconstruct surface structures include “region growing” methods. Similar techniques also exist for segmenting range images. Another group of solutions deals with a limited class of objects that can be bounded only by simple surfaces.